FIG. 1 is a highly simplified view of a conventional packet-switched computer network (“computer network”). The computer network includes “routers”, which are intelligent devices that control the flow of information through the network. The routers are interconnected by transmission facilities (“links”), such as electrical cables, fiber-optic cables, or wireless-transmission facilities. The computer network enables “hosts”, which are typically the source or destination of information transported by the network, to exchange information with each other. To exchange information with another host, an origination host places the information to be transported (“application data,” which is typically data from the application-layer software of the system) into a “packet” (a specially formatted sequence of bits typically handled by the network-layer software and/or hardware), and transmits the packet to a router in the network. This packet is “forwarded” from one router to another until the final router transmits the packet to the destination host (See “The Catenet Model for Internetworking” by Vint Cerf, Internet Engineering Note 48 (IEN48), July 1978, Defense Advanced Research Projects Agency, Information Processing Techniques Office; available at internet web-address isi.edu/in-notes/ien/ien48.txt, which is incorporated herein by reference).
FIG. 2 illustrates the structure of a typical packet that includes a “packet header” and “packet data”. The packet header contains control information that influences how the packet is processed, while the packet data is the information that the packet is transporting. The packet header may include several sequences of contiguous bits (“fields”), such as a field that identifies the origination host or a field that identifies the destination host. In some protocols, the packet header includes two components: a fixed-length header, which is always present, and a variable-length header, which is optional.
The processing of packets by hosts and routers is controlled by network protocols (“protocols”), which specify the format of packets and the procedures for exchanging packets. The protocols used in the Internet are often referred to as “the Internet protocol suite”. The Internet protocol suite employs the concept of “protocol layering”, where the packet-data portion of a packet may contain a complete packet of another, generally “higher layer” protocol.
FIG. 3 illustrates the protocol layering that is used by the Internet protocol suite. A “link protocol” controls the transfer of packets between adjacent network nodes (e.g., hosts or routers); a wide variety of link protocols are used with the Internet protocol suite. A “network protocol” controls the transfer of packets between the origination network node and the destination network node; only one network protocol is included in the Internet protocol suite, namely the Internet Protocol (IP). A “transport protocol” ensures that information is transferred reliably between the origination and destination network nodes; many transport protocols are included in the Internet protocol suite, such as the Transmission Control Protocol (TCP) (which is specified by Postel, Jon, Ed., “Transmission Control Protocol”, RFC 793, September 1981, University of Southern California, Information Sciences Institute; which is incorporated herein by reference). An application protocol is, from the perspective of the Internet protocol suite, the ultimate originator or consumer of data; numerous application protocols are included in the Internet protocol suite, such as the Hypertext Transfer Protocol (HTTP) (which is specified by Fielding, Roy T., et. al, “Hypertext Transfer Protocol—HTTP/1.1”, RFC 2616, June 1999, Internet Engineering Task Force; which is incorporated herein by reference), which controls the transfer of information between a Web server and a Web browser.
Two major versions of the Internet Protocol have been specified, IP Version 4 (“IPv4”) (specified by Postel, Jon, Ed., “Internet Protocol”, RFC 791, September 1981, University of Southern California, Information Sciences Institute; which is incorporated herein by reference), which is widely deployed, and IP Version 6 (“IPv6”) (specified by Deering, Stephen and Robert Hinden, “Internet Protocol, Version 6 (IPv6) Specification”, RFC 2460, December 1998, Internet Engineering Task Force; which is incorporated herein by reference), which may become widely deployed in the future. The IPv4 and IPv6 packet headers contain both a fixed-length header and a variable-length header. The IPv4 variable-length header is called the “IP Options”, while the IPv6 variable-length header is called the “Extension Headers”.
An important security component of the Internet protocol suite is the Internet Security (IPsec) protocols (which are described by Kent, Stephen and Karen Seo, “Security Architecture for the Internet Protocol”, RFC 4301, December 2005, Internet Engineering Task Force; which is incorporated herein by reference). The Encapsulating Security Protocol (ESP) (which is specified in a document by Kent, Stephen, “IP Encapsulating Security Payload (ESP)”, RFC 4303, December 2005, Internet Engineering Task Force; which is incorporated herein by reference), one of the IPsec protocols, transports or “encapsulates” an IP packet that is to be protected within another, “encapsulating” IP packet. The encapsulated IP packet may be encrypted, which prevents the disclosure of the contents of the encapsulated IP packet, either its packet header or its packet data, to any system that does not possess the appropriate cryptographic keys.
FIG. 4 is a highly abstracted summary of the major components of a typical router (a summary of the structure and operation of a router can be found in a document by Baker, Fred, Ed., “Requirements for IP Version 4 Routers”, RFC 1812, June 1995, Internet Engineering Task Force; which is incorporated herein by reference). An “interface” connects the router to a link; a router may have several interfaces and be connected to several links. An interface has associated with it one or more “transmit queues”, which hold packets that are waiting to be transmitted on the interface. These transmit queues may have different priorities, such that packets in a higher-priority queue are likely to be transmitted before packets in a lower-priority queue. A router generally contains one or more programmable computers, and as a result contains “router software”. The router software performs many functions, include “forward incoming packet”. A “router configuration” is information that guides the overall operation of a specific router, is typically created manually, and is generally fairly static. A “route information base” contains information about which router a packet should be forwarded to in order to eventually reach a particular destination, and is often updated dynamically to quickly reflect changes in the network.
Routers process network-layer-protocol packets, such as IP packets in the Internet protocol suite. The forward-incoming-packet software processes a packet received from an interface (an “incoming packet”). The forward-incoming-packet software determines how an incoming packet should processed based on information contained in the packet header of the IP packet, information contained in the router configuration, information contained in the route information base, and possibly other information. This software may determine that an incoming packet should be placed in a particular transmit queue for transmission on a specific interface, that an incoming packet should be discarded (“dropped”), that some other packet should be dropped, or that some other action should be taken. Because the principal function of routers is to process network-layer packets, they are sometimes referred to as “network-layer devices”.
As the speed of links has increased dramatically over the last two decades, the time within which the forward-incoming-packet software must process an incoming packet has decreased correspondingly. As a result, router vendors have traditionally strived to simplify the decisions that the forward-incoming-packet software must make. This is particularly true in very high-speed routers that must support link speeds of many gigabits-per-second, where the computational capacity of the router, rather than the bandwidth of the links, is often the scarce resource that needs to be conserved.
A. Quality of Service (QoS) Background
In many environments, it is highly desirable for a network to treat some packets differently than others, based on one or more characteristics of the packets. One important characteristic of a packet is the type of application data that it is transporting. For example, it is often beneficial to ensure that packets carrying voice data (e.g., real-time telephone calls) are moved through the network more quickly than packets that are carrying application data that are less sensitive to delay. When a network provides different levels of services to different packets based on some of their characteristics, the network is said to provide “quality-of-service (QoS) assurances”. In order to make the task of providing QoS assurances more tractable, packets are sometimes grouped into “flows”, where a flow is all of the packets that are part of a particular connection between an application on one host and another application on another host. Another approach is to categorize packets into different “traffic classes” or “classes of traffic”. For example, packets carrying voice data may be considered one class of traffic, while packets carrying file-transfer data may be considered another class of traffic.
Numerous QoS objectives have been previously described, such as ensuring that all of the packets in a particular flow or traffic class receive at least a certain amount of bandwidth, ensuring that certain packets are transported through the network within some specified period of time, or ensuring that the variance in the time that it takes certain packets to be transported through the network is below some specified value. Many other QoS objectives could be and have been described, although most of them have been fairly simple.
Numerous techniques have been developed that enable a router to implement or “enforce” QoS assurances. These techniques include assigning multiple, prioritized transmit queues to each interface; managing the transmit queues (such as deciding which packets to discard when a queue starts to become full); measuring and controlling the amount of bandwidth that is made available to a particular flow or traffic class; as well as numerous other techniques.
The Internet architecture includes two QoS models, or general strategies for providing QoS assurances: the Integrated Services model and the Differentiated Services model.
The Integrated Services model (described by Baden, Robert, David Clark, and Scott Shenker, “Integrated Services in the Internet Architecture: an Overview”, RFC 1633, June 1994, Internet Engineering Task Force; which is incorporated herein by reference), enables an application to reserve network resources, such as link bandwidth or transmit queue space, for a flow. An application may reserve network resources by sending a request through the network to the application with which it intends to communicate. The routers along the path may reserve for the flow resources, if they are available, in response to the request. All packets within a flow receive the same level of service. The level of service received by the packets within a flow is only indirectly related to the content, meaning, importance, and/or other attributes of the application data transported by the packets. The Integrated Services model has not been widely deployed, in large part because it does not scale well (i.e., it impedes the deployment and operation of very large networks because the routers in the core of a very large network must manage a very large number of reservations). Additionally, the Integrated Services model does not respond well to changes in the route that the packets of a flow take through the network, because after a route changes, the locations of the reserved resources no longer match the routers through with the packets are forwarded.
The Differentiated Services model (summarized by Blake, Steven, et. al, “An Architecture for Differentiated Services”, RFC 2475, December 1998, Internet Engineering Task Force; which is incorporated herein by reference), classifies all packets into as many as sixty-four different traffic classes and potentially provides a different level of service to each of these traffic classes. A six-bit field in the fixed header of IP packets, called the Differentiated Services Code Point (DSCP), identifies the traffic class to which a packet belongs. All packets within a traffic class receive the same level of service. The level of service received by the packets within a traffic class is manually configured, generally does not change once the network has been configured, and is only indirectly related to the content, meaning, importance, and/or other attributes of the application data transported by the packets. The Differentiated Services model scales well, because even routers in very large networks need to support at most sixty-four different classes of traffic. However, because the differentiated services model can support only a limited number of traffic classes, it can provide only very coarse-grained QoS assurances. The initial version of the IPsec ESP interfered with the use of the Differentiated Services model because the DSCP field in the original, encapsulated packet was inaccessible to routers when encryption was employed. An updated version of the ESP specification permits the encrypting node to copy the DSCP field from the header of the encapsulated IP packet into the DSCP field of the header of the encapsulating IP packet. This permits routers to access the copy of the DSCP field that is in the packet header of the encapsulating packet, without necessarily being able to decrypt the encrypted, encapsulated packet.
B. Ad Hoc Networks Background
Technology advances have enabled the development of mobile, ad hoc, wireless networks (“ad hoc networks”). The behavior of ad hoc networks contrasts sharply with that of traditional, wired networks. In ad hoc networks, network nodes (which generally perform the functions of both hosts and routers), configure themselves into a network without manual intervention, whereas the topologies (the global structure of the links, the routers, and the interconnections between them), of wired networks are generally designed and configured manually. The topologies of ad hoc networks may change repeatedly and rapidly as nodes move or wireless propagation changes, which contrasts with the much more stable topologies of wired networks. The error rates of wireless links are generally many orders of magnitude higher than those for most wired links, and the bandwidth of wireless links may change over time as propagation conditions change, unlike the fixed bandwidth of wired links.
Developing technologies to provide QoS assurances in the highly dynamic environments presented by ad hoc networks has proven to be difficult. Efforts have been made to adapt the Integrated Services model (such as that described by Lee, Seoung-Bum and Andrew T. Campbell, “INSIGNIA: In-Band Signaling Support for QoS in Mobile Ad Hoc Networks”, Proc. of 5th International Workshop on Mobile Multimedia Communications (MoMuC '98), Berlin Germany, October 1998; which is incorporated herein by reference), and the Differentiated Services model (such as that proposed by Gahng-Seop, Ahn, Andrew T. Campbell, Andras Veres and Li-Hsiang Sun, “SWAN: Service Differentiation in Stateless Wireless Ad Hoc Networks”, Proc. IEEE INFOCOM 2002, New York, N.Y., June 2002; which is incorporated herein by reference), for use in ad hoc networks. However, these efforts have not been particularly effective. Topology changes quickly make reservations, such as those used in the Integrated Services model, moot. The limited number of traffic classes supported by the Differentiated Services model often does not provide enough granularity to quickly adapt to rapidly changing network topologies or link bandwidths. Furthermore, any QoS architecture that relies upon a node knowing or predicting the current network topology, current traffic patterns or current link bandwidths beyond its immediate vicinity is not likely to be effective in these potentially highly dynamic environments.
The bandwidths of the wireless links typically used in ad hoc networks are generally substantially lower that those used in wired networks, often tens or hundreds of kilobits-per-second, rather than as much as many gigabits-per-second. As a result, link bandwidth, rather than the computational capacity of the router, is often the scarce resource that needs to be conserved.
Publish/Subscribe Background
The “publish/subscribe” model for information dissemination describes a means by which an originator can disseminate information to multiple receivers that have expressed a desire to receive that information (such as the specification by OBJECT MANAGEMENT GROUP, Data Distribution Service for Real-Time Systems Specification, December 2005, Object Management Group, Inc.; which is incorporated herein by reference). In the publish/subscribe model, a node “publishes”, or makes available, updated information from time to time. This updated information is transported in “messages”. Other nodes “subscribe” to, or request to receive, certain information updates as they are published. An underlying dissemination infrastructure isolates a publisher and its subscribers, and ensures that published information is efficiently transmitted to all subscribed nodes. The publisher is generally not aware of the identity or, or even the number of, active subscribers. The published information is categorized into “topics”, and nodes can subscribe to one or more specific topics, for example, stock market quotes. A message related to a specific topic may have several “attributes” associated with it. For example, messages that are part of the “stock market quote” topic may include an attribute that contains the name of the company for which the stock price is quoted. The publish/subscribe model permits a node to subscribe to receive only those messages within a topic whose attributes match some criteria. For example, a node might subscribe to receive only those messages in the “stock market quote” topic for which the “company name” attribute matches some specific value.
Many protocols and architectures have been developed to provide publish/subscribe services. These specifications generally focus on the behavior of applications (application-layer software) and application-layer protocols. In particular, most publish/subscribe specifications are silent on precisely how messages should be disseminated to subscribers and even whether messages should be disseminated efficiently.
A number of prior art works relate to the packet-forwarding part of the present invention: U.S. Pat. No. 6,044,080 to Antonov (filed Nov. 19, 1996, issued Mar. 28, 2000), U.S. Pat. No. 6,046,980 to Packer (filed Nov. 24, 1997, issued Apr. 4, 2001), U.S. Pat. No. 6,285,679 to Dally et al. (filed May 26, 1998, issued Sep. 4, 2001), U.S. Pat. No. 6,452,933 to Duffield et al. (filed Nov. 18, 1997, issued Sep. 17, 2002), U.S. Pat. No. 6,975,638 to Chen et al. (filed Oct. 13, 2000, issued Dec. 13, 2005), U.S. Pat. No. 7,187,679 to Dally et al. (filed Sep. 18, 2002, issued May 6, 2007) and U.S. Pat. No. 7,274,700 to Jin et al. (filed Sep. 26, 2002, issued Sep. 25, 2007), each of which is incorporated herein. However, these works are neither necessary nor sufficient for all embodiments of the present invention to achieve the objectives and advantages of the present invention.